package com.wang.sort3;

import java.util.HashMap;
import java.util.List;
import java.util.Stack;

/**
 * @Author: along
 * @Create: 2021/4/23
 * @Description:返回user的个数
 */
public class Demo07_MergerUsers {
    public static class User{
        public String a;
        public String b;
        public String c;

        public User(String a, String b, String c) {
            this.a = a;
            this.b = b;
            this.c = c;
        }
    }
    public static class Node<V> {
        V value;

        public Node(V v) {
            this.value = v;
        }
    }
    public static class UnionSet<V> {
        public HashMap<V, Demo06_UnionFind.Node<V>> nodes; //节点的对应表
        public HashMap<Demo06_UnionFind.Node<V>, Demo06_UnionFind.Node<V>> parents;//节点的代表点 这里成为parents
        public HashMap<Demo06_UnionFind.Node<V>, Integer> sizeMap;//代表点的map的长度
        //初始化
        public UnionSet(List<V> values) {
            for (V value: values
            ) {
                Demo06_UnionFind.Node<V> node = new Demo06_UnionFind.Node<>(value);
                nodes.put(value, node);
                parents.put(node, node);
                sizeMap.put(node, 1);
            }
        }

        public boolean isSameSet(V a, V b ) {
            if(!nodes.containsKey(a) || !nodes.containsKey(b)){
                return false;
            }
            return findFather(nodes.get(a)) == findFather(nodes.get(b));
        }

        public void union(V a, V b) {
            if(!nodes.containsKey(a) || !nodes.containsKey(b)) {
                return;
            }
            Demo06_UnionFind.Node<V> aHead = findFather(nodes.get(a));
            Demo06_UnionFind.Node<V> bHead = findFather(nodes.get(b));
            if(aHead != bHead) {
                int aSetSize = sizeMap.get(aHead);
                int bSetSize = sizeMap.get(bHead);
                if(aSetSize >= bSetSize) {
                    parents.put(bHead, aHead);
                    sizeMap.put(aHead, aSetSize + bSetSize);
                    parents.remove(bHead);
                }
                else {
                    parents.put(aHead, bHead);
                    sizeMap.put(bHead, aSetSize + bSetSize);
                    parents.remove(aHead);
                }
            }
        }

        private Demo06_UnionFind.Node<V> findFather(Demo06_UnionFind.Node<V> cur) {
            Stack<Demo06_UnionFind.Node<V>> path = new Stack<>();//初始化一个栈，来保存遍历过程中代表点为同一个的节点
            //从cur开始，一直往上找，找到不能往上的节点，即为代表点，返回
            while (cur != parents.get(cur)) {
                path.push(cur);
                cur = parents.get(cur);
            }
            //上面的while跳出后，cur一定来到代表点
            //优化
            while (!path.isEmpty()) {
                //返回cur之前，把所有的遍历到的代表点为cur的节点在parents中的代表节点改为cur
                parents.put(path.pop(), cur);
            }
            return cur;
        }

        public int getSetsNum() {
            return sizeMap.size();
        }
    }


    //如果两个user，a字段一样或者b字段一样或者c字段一样 就认为是同一个user
    //合并两个user 返回合并后的用户数量
    public static int mergeUsers(List<User> users) {
        UnionSet<User> unionFind = new UnionSet<>(users);
        HashMap<String, User> mapA = new HashMap<>();
        HashMap<String, User> mapB = new HashMap<>();
        HashMap<String, User> mapC = new HashMap<>();

        for (User user: users
             ) {
            if(mapA.containsKey(user.a)) {
                unionFind.union(user, mapA.get(user.a));
            }
            else {
                mapA.put(user.a, user);
            }
            if(mapB.containsKey(user.b)) {
                unionFind.union(user, mapB.get(user.b));
            }
            else {
                mapB.put(user.b, user);
            }
            if(mapC.containsKey(user.c)) {
                unionFind.union(user, mapC.get(user.c));
            }
            else {
                mapC.put(user.c, user);
            }
        }
        //向并查集询问，还剩多少个集合
        return unionFind.getSetsNum();
    }
}
